AlesPalla (Normal User)
Rookie
 
Messaggi: 25
Iscritto: 23/11/2008
|
Allora ho appena creato un algoritmo che mescola un mazzo da 40 carte..
Per generarlo ho pensato di creare un vettore di 40 int che associa ad ogni numero la sua posizione...
Per creare il vettore io ho usato questo algoritmo fatto da me:
Codice sorgente - presumibilmente C++ |
void genera_pos(int*p){ int c; srand(time(0)); unsigned long int a=0; //vettore di bit utilizzato come contatore for (int i=0;i<40;i++){ c=numero_cas(0,40); if (((1<<c)&a)==0){ //verifica se il c-esimo bit è acceso p[i]=c; a|=(1<<c); //accende il c-esimo bit } else { i--; //decrementa e fa in modo di reiterare il ciclo } }
|
e per generare il numero casuale ho usato questo che è + o - standard:
Codice sorgente - presumibilmente C/C++ |
int numero_cas(int iniz,int fin){
return rand()%fin +iniz ;
}
|
Il problema è che l'algoritmo funziona BENISSIMO fino tipo al 24 numero...poi si blocca inspiegabilmente...
secondo voi cosa è sbagliato? |
|
|
AlesPalla (Normal User)
Rookie
Messaggi: 25
Iscritto: 23/11/2008
|
Ho scoperto cosa non andava:
Vacendo correre il programma diverse volte ho osservato che si bloccava sempre in punti diversi ho ipotizzato che finissero i numeri della sequenza e ho modificato in questa maniera il codice:
Codice sorgente - presumibilmente C++ |
void genera_pos(int*p){ int c,d=0; srand(time(0)); unsigned long int a=0; //contatore for (int i=0;i<40;i++){ c=numero_cas(0,40); if (((1<<c)&a)==0){ //verifica se il c-esimo bit è acceso p[i]=c; a|=(1<<c); //accende il c-esimo bit d=0; } else { i--; //decrementa e fa in modo di reiterare il ciclo if(++d>100) {cout<<"Hey srand si e' bloccato!\n";return;} } } cout<<'\n'; }
|
E sembrerebbe che abbia ragione.. come posso fare per porvi rimedio?
|
|
|
Lawliet (Normal User)
Expert
Messaggi: 386
Iscritto: 09/04/2009
|
Postato originariamente da pierotofy:
operazioni bit-wise |
Ecco cosa sono, non ho mai avuto a che fare con questi tipo di operazioni.
EDIT: ho cancellato ciò che ho scritto prima ^^' Ultima modifica effettuata da Lawliet il 23/11/2009 alle 22:56 |
|
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Non ho eseguito il codice e non ho analizzato per bene tutto il funzionamento, ma so che non dovresti mai modificare il valore di 'i' all'interno del ciclo (e' semanticamente sbagliato). Mi sembra che con tutti questi puntatori e operazioni bit-wise stai ingrandendo il problema... per mescolare un mazzo di carte assegni ad ogni carta un valore casuale (da 1 a N anche con ripetizioni, dove N >= 40), dopodiche' ordini la lista di carte in base al valore assegnato casualmente.
Perche' tirare in ballo operazioni bit-wise? A meno che non stai mescolando un mazzo di qualche migliaio di milioni di carte la differenza non si nota usando operatorazioni normali (e piu' leggibile da parte di un altro programmatore).
Ultima modifica effettuata da pierotofy il 23/11/2009 alle 22:47
|
|
|
gigisoft (Member)
Guru
Messaggi: 696
Iscritto: 11/10/2008
|
Postato originariamente da pierotofy:
Non ho eseguito il codice e non ho analizzato per bene tutto il funzionamento, ma so che non dovresti mai modificare il valore di 'i' all'interno del ciclo (e' semanticamente sbagliato). Mi sembra che con tutti questi puntatori e operazioni bit-wise stai ingrandendo il problema... per mescolare un mazzo di carte assegni ad ogni carta un valore casuale (da 1 a N anche con ripetizioni, dove N >= 40), dopodiche' ordini la lista di carte in base al valore assegnato casualmente.
Perche' tirare in ballo operazioni bit-wise? A meno che non stai mescolando un mazzo di qualche migliaio di milioni di carte la differenza non si nota usando operatorazioni normali (e piu' leggibile da parte di un altro programmatore). |
Concordo pienamente,
in alternativa, volendo rendere il mescolamento un po' meno pseudo e piu' casuale, nel progetto Clondike io usai un algoritmo forse piu' complesso, ma che simulava meglio un mescolamento reale, in pratica usavo una lista di oggetti "Carta" dopodiche' per un alto numero di volte ( 1000 se non ricordo male ) prendevo la prima carta della lista e la mettevo in una posizione scelta a caso, poi ripetevo lo stesso procedimento, però prendendo l'ultima.
Ciao. 
Luigi. |
|
|
TheKaneB (Member)
Guru^2
Messaggi: 1792
Iscritto: 26/06/2009
|
Per mescolare un mazzo di carte esiste un algoritmo molto semplice e molto efficiente inventato da Knuth.
In sostanza funziona così:
Hai un array di MAX elementi.
Hai bisogno di mescolare un numero di elementi pari a M.
0) LIMITE = MAX - M
1) N = MAX - 1
2) se N == LIMITE vai a 7)
3) fai il random tra 0 e N, chiamiamolo R.
4) prendi il numero di posto R e lo scambi con il numero di posto N
5) N = N - 1
6) ritorna al 2)
7) metti in output tutti gli elementi dal posto LIMITE al posto MAX-1
Come caso particolare, se vuoi mescolare tutto il mazzo, basta porre M = MAX, oppure (che è uguale) basta mettere LIMITE = 0.
Spero ti sia utile 
PS: Riguardo al tuo codice, non puoi shiftare a sinistra di 40 bit un intero di tipo long, perchè normalmente un long ha 32bit su una tipica macchina desktop. Usa long long se proprio vuoi 64 bit di dati, ma ti sconsiglio questo approccio perchè non è generico e non è portabile, e inoltre le operazioni bitwise dovrebbero essere usate solo in caso di necessità ben precise; ad esempio nel digital signal processing, oppure in routine estremamente ottimizzate per funzionare su particolari architetture che hanno gli shift "gratis" come ARM.
|
|
|
HeDo (Founder Member)
Guru^2
Messaggi: 2765
Iscritto: 21/09/2007
|
non per sminuire la soluzione di kane ma potresti semplicemente generare un mazzo ordinato e poi scambiare 2 carte a caso tante volte quante sono le carte del mazzo. dovrebbe essere sufficiente no?
oltretutto lo trovo il modo più semplice 
|
|
|
TheKaneB (Member)
Guru^2
Messaggi: 1792
Iscritto: 26/06/2009
|
Certo anche la tua è un'ottima soluzione. Ho voluto citare l'algoritmo di Knuth giusto per mettere un po' di "letteratura classica" in gioco 
Oltretutto è un sistema generico, che ti consente di avere anche soltanto un sottoinsieme scombinato, in modo semplice ed efficiente. Comunque è sempre divertente confrontare gli algoritmi per così dire "greedy", cioè quelli che ci vengono in testa sulle prime, con gli algoritmi "di letteratura" sui quali molti studiosi (soprattutto teorici) hanno lavorato negli anni.
Ciao!
|
|
|
AlesPalla (Normal User)
Rookie
Messaggi: 25
Iscritto: 23/11/2008
|
Grazi 1000 per le risposte!!
Ho implementato l'algoritmo di Kane e funziona a meraviglia!!
|
|
|
![C/C++ - Mescolare un mazzo di carte [C++]](/data/logos/logositov9.png)
